package week_08;


public class ImplementStrstr_28 {
    // 实现robin-krap算法


    //O(1) 时间复杂度
    int b = 131;
    int p = (int) (1e9 + 7);

    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;

        int n = haystack.length();
        int m = needle.length();
        // 规整从1开始计算
        String s = " " + haystack;
        String t = " " + needle;


        // 计算前i个字符的hash值
        long[] h = new long[n + 1];
        long[] p131 = new long[n + 1];
        h[0] = 0;
        p131[0] = 1;
        for (int i = 1; i <= n; i++) {
            //𝐻[𝑖]=Hash(𝑠[0...𝑖−1])= 𝐻[𝑖−1]∗𝑏+[𝑠𝑖−1]mod 𝑝
            h[i] = (h[i - 1] * b + s.charAt(i) - 'a' + 1) % p;
            p131[i] = (p131[i - 1] * b) % p;
        }

        long THASH = 0;
        for (int i = 1; i <= m; i++) {
            THASH = (THASH * b + t.charAt(i) - 'a' + 1) % p;
        }

        // 计算s中m长度的子串的hash值是否相等THASH
        for (int i = m; i <= n; i++) {
            System.out.println(subHash(i - m + 1, i, h, p131));
            // 计算前i - 前（i-m+1）的子串hash值
            if (subHash(i - m + 1, i, h, p131) == THASH &&
                    s.substring(i - m + 1, i + 1).equals(t.substring(1))
            ) return i - m;
        }

        return -1;
    }

    public int subHash(int l, int r, long[] h, long[] p131) {
        //𝐻[5]–𝐻[2]∗𝑏3
        //fooba−fo000=oba
        //Hash(𝑠𝑙...𝑟)=(𝐻[𝑟+1]−𝐻[𝑙]∗(pow(𝑏,𝑟−𝑙+1) )mod 𝑝
        return (int) ((h[r] - h[l - 1] * p131[r - l + 1]) % p + p) % p;
    }


    public int strStr2(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        if (n == 0 && m == 0) return 0;
        for (int i = 0; i < n; i++) {
            int idx = 0;
            while (idx < m && idx + i < n && haystack.charAt(i + idx) == needle.charAt(idx)) {
                //  System.out.println(haystack.charAt(i+idx)+":"+needle.charAt(idx)+":"+i+":"+idx);
                idx++;
            }
            // idx 加了多少次 就是多长的字符串
            if (idx == m) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        String s1 = "hello";
        String s2 = "ll";
        ImplementStrstr_28 test = new ImplementStrstr_28();
        System.out.println(test.strStr(s1, s2));
        ;
    }
}
